Covering arrays on graphs: qualitative independence graphs and extremal set partition theory

摘要

The main focus of this thesis is a generalization of covering arrays,covering arrays on graphs. Two vectors v,w in Z_k^n are qualitativelyindependent if for all ordered pairs (a,b) in Z_k x Z_k there is a position iin the vectors where (a,b) = (v_i,w_i). A covering array is an array with theproperty that any pair of rows are qualitatively independent. A covering arrayon a graph is an array with a row for each vertex of the graph with theproperty that any two rows which correspond to adjacent vertices arequalitatively independent. The addition of a graph structure to covering arraysmakes it possible to use methods from graph theory to study these designs. Inthis thesis, we define a family of graphs called the qualitative independencegraphs. A graph has a covering array, with given parameters, if and only ifthere is a homomorphism from the graph to a particular qualitative independencegraph. Cliques in qualitative independence graphs relate to covering arrays andindependent sets are connected to intersecting partition systems. It is knownthat the exact size of an optimal binary covering array can be determined usingSperner's Theorem and the Erdos-Ko-Rado Theorem. Since the rows of generalcovering arrays correspond to set partitions, we give extensions of Sperner'sTheorem and the Erdos-Ko-Rado Theorem to set-partition systems. We alsoconsider a subgraph of a general qualitative independence graph called theuniform qualitative independence graph. We give the spectra for several ofthese graphs and conjecture that they are graphs in an association scheme. Wealso give a new construction for covering arrays which yields many new upperbounds on the size of optimal covering arrays.